package com.lun.easy;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.lun.util.BinaryTree.TreeNode;

public class CousinsInBinaryTree {
    
	//方法一：BFS
	public boolean isCousins(TreeNode root, int x, int y) {

    	LinkedList<TreeNode> queue = new LinkedList<>();
    	List<Integer> tempList = new ArrayList<>();
    	queue.offer(root);
    	int depth = 0;
    	
    	checkNode(null, root, x, y, depth, tempList);
    	while(!queue.isEmpty()) {
    		
    		depth++;
    		for(int size = queue.size(); size > 0; size--) {
    			
    			TreeNode node = queue.poll();
    			
    			if(node.left != null) {
    				if(checkNode(node, node.left, x, y, depth, tempList))
    					return true;
    				queue.offer(node.left);
    			}
    			
    			if(node.right != null) {
    				if(checkNode(node, node.right, x, y, depth, tempList))
    					return true;
    				queue.offer(node.right);
    			}
    		}
    	}
    	
    	return false;
    }
    
    private boolean checkNode(TreeNode parent, TreeNode child, int x, int y, int depth, List<Integer> list) {
    	
    	if(child.val == x || child.val == y) {
    		list.add(parent == null? -1 : parent.val);
    		list.add(depth);
    	}
    	
    	if(list.size() == 4) {
        	//different parent and same depth
        	if(list.get(0) != list.get(2) && list.get(1) == list.get(3))
        		return true;
    	}
    	return false;
    }


    //方法二：DFS
    public boolean isCousins2(TreeNode root, int x, int y) {
    	return dfs(null, root, x, y, 0, new ArrayList<>());
    }
    
    private boolean dfs(TreeNode parent, TreeNode child, int x, int y, int depth, List<Integer> list) {
    	if(child == null) return false;
    	
    	if(child.val == x || child.val == y) {
    		list.add(parent == null ? -1 : parent.val);
    		list.add(depth);
    	}
    	
    	if(list.size() == 4) {
        	//if different parent and same depth is true, return true
        	if(list.get(0) != list.get(2) && list.get(1) == list.get(3))
        		return true;
    	}
    	
    	return dfs(child, child.left, x, y, depth + 1, list) || // 
    			dfs(child, child.right, x, y, depth + 1, list);
    }
    
}
